package codingforgreat.lchot150;

public class Lc004 {
    //俩黑盒实现：1.两个有序数组第k小 2.找两个有序数组等长段中上中位数
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int size = nums1.length + nums2.length;
        boolean even = (size & 1) == 0;
        if (nums1.length != 0 && nums2.length != 0) {
            if (even) {
                return (double) (findKthNum(nums1, nums2, size / 2) + findKthNum(nums1, nums2, size / 2 + 1)) / 2D;
            } else {
                return findKthNum(nums1, nums2, size / 2 + 1);
            }
        } else if (nums1.length != 0) {
            if (even) {
                return (double) (nums1[(size - 1) / 2] + nums1[size / 2]) / 2;
            } else {
                return nums1[size / 2];
            }
        } else if (nums2.length != 0) {
            if (even) {
                return (double) (nums2[(size - 1) / 2] + nums2[size / 2]) / 2;
            } else {
                return nums2[size / 2];
            }
        } else {
            return 0;
        }
    }
    //黑盒1 ： 找两个有序数组第k小的数
    public int findKthNum(int[] nums1,int[] nums2,int k){
        int[] longs = nums1.length > nums2.length ? nums1 : nums2;
        int[] shorts = longs == nums1 ? nums2 : nums1;
        int l = longs.length;
        int s = shorts.length;
        if(k <= s){
            return getMdiUp(shorts,longs,0,k - 1,0,k - 1);
        }else if(k > l){
            if(longs[k - s -1] >= shorts[s - 1]){
                return longs[k - s -1];
            }
            if(shorts[k - l - 1] >= longs[l - 1]){
                return shorts[k - l - 1];
            }
            return getMdiUp(shorts,longs,k - l,s - 1,k - s,l - 1);
        }else{ // s < k <= l
            if(longs[k - s -1] >= shorts[s - 1]) {
                return longs[k - s -1];
            }
            return getMdiUp(shorts,longs, 0,s -1,k - s,k - 1);
        }
    }
    //计算上中位数
    public int getMdiUp(int[] nums1,int[] nums2,int s1,int e1,int s2,int e2){
        int mid1 = 0;
        int mid2 = 0;
        while(s1 < e1){
            mid1 = (s1 + e1)/2;
            mid2 = (s2 + e2)/2;
            if(nums1[mid1] == nums2[mid2]){
                return nums1[mid1];
            }
            if(((e1 - s1 + 1 ) & 1) == 0){//偶数
                if(nums1[mid1] > nums2[mid2]){
                    e1 = mid1;
                    s2 = mid2 + 1;
                }else{
                    e2 = mid2;
                    s1 = mid1 + 1;
                }
            }else{
                if (nums1[mid1] > nums2[mid2]) {
                    if (nums2[mid2] >= nums1[mid1 - 1]) {
                        return nums2[mid2];
                    }
                    e1 = mid1 - 1;
                    s2 = mid2 + 1;
                } else { // A[mid1] < B[mid2]
                    if (nums1[mid1] >= nums2[mid2 - 1]) {
                        return nums1[mid1];
                    }
                    e2 = mid2 - 1;
                    s1 = mid1 + 1;
                }
            }
        }
        return Math.min(nums1[s1],nums2[s2]);
    }
}
